use std::collections::BTreeMap;
use std::fs::File;
use std::io::{self, Read};

struct Dsu<T>
where T: Eq + Ord + Clone {
    data: BTreeMap<T, T>,
}

impl<T> Dsu<T>
where T: Eq + Ord + Clone {
    pub fn new() -> Self {
        Self { data: BTreeMap::new() }
    }
    pub fn getf(&mut self, x: T) -> T {
        if let Some(fa) = self.data.get(&x) {
            if *fa != x {
                let ret = self.getf(fa.clone());
                self.data.insert(x.clone(), ret.clone());
                ret
            } else {
                x.clone()
            }
        } else {
            self.data.insert(x.clone(), x.clone());
            x
        }
    }
    pub fn merge(&mut self, x: T, y: T) -> bool {
        let x = self.getf(x);
        let y = self.getf(y);
        if x == y {
            false
        } else {
            self.data.insert(x, y);
            true
        }
    }
    pub fn unique_count(&self) -> u32 {
        self.data.iter().filter(|(key, value)| key == value).count() as u32
    }
    
}

fn work2(key: &str, value: &str, dsu: &mut Dsu<String>) {
    let key = key.trim();
    let value = value.trim();
    assert!(value.starts_with("["));
    assert!(value.ends_with("]"));
    let value = &value[1..value.len()-1];
    let mut value = value.trim().chars();
    let mut s = String::new();
    let mut in_str = false;
    while let Some(ch) = value.next() {
        if ch == '"' {
            in_str = !in_str;
        }
        if in_str == false && ch == ',' {
                dsu.merge(key.to_string(), s.trim().to_string());
                s.clear();
        } else {
            s.push(ch);
        }
    }
    dsu.merge(key.to_string(), s.trim().to_string());
}

fn work1(input: &str) -> u32 {
    let mut dsu = Dsu::<String>::new();
    let input = input.trim();
    assert!(input.starts_with("{"));
    assert!(input.ends_with("}"));
    let mut input = input[1..input.len()-1].trim().chars();
    let mut ret = Vec::new();
    let mut key = String::new();
    let mut value = String::new();
    let mut is_value = false;
    let mut in_str = false;
    let mut bracket_depth = 0;
    while let Some(ch) = input.next() {
        if ch == '"' {
            in_str = !in_str;
        } else if in_str == false {
            if ch == '{' || ch == '[' {
                bracket_depth += 1;
            } else if ch == '}' || ch == ']' {
                bracket_depth -= 1;
            }
        }
        if in_str == false && bracket_depth == 0 && ch == ':' {
                is_value = true;
        } else if in_str == false && bracket_depth == 0 && ch == ',' {
                ret.push(work2(&key, &value, &mut dsu));
                key.clear();
                value.clear();
                is_value = false;
        } else if is_value == false {
            key.push(ch);
        } else {
            value.push(ch);
        }
    }
    ret.push(work2(&key, &value, &mut dsu));
    dsu.unique_count()
}

fn work(input: &str) -> Vec<u32> {
    let input = input.trim();
    assert!(input.starts_with("{"));
    assert!(input.ends_with("}"));
    let mut input = input[1..input.len()-1].trim().chars();
    let mut ret = Vec::new();
    let mut key = String::new();
    let mut value = String::new();
    let mut is_value = false;
    let mut in_str = false;
    let mut bracket_depth = 0;
    while let Some(ch) = input.next() {
        if ch == '"' {
            in_str = !in_str;
        } else if in_str == false {
            if ch == '{' || ch == '[' {
                bracket_depth += 1;
            } else if ch == '}' || ch == ']' {
                bracket_depth -= 1;
            }
        }
        if in_str == false && bracket_depth == 0 && ch == ':' {
                is_value = true;
        } else if in_str == false && bracket_depth == 0 && ch == ',' {
                ret.push(work1(&value));
                key.clear();
                value.clear();
                is_value = false;
        } else if is_value == false {
            key.push(ch);
        } else {
            value.push(ch);
        }
    }
    ret.push(work1(&value));
    ret
}

fn read_file(file_path: &str) -> Result<String, io::Error> {
    let mut file = File::open(file_path)?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
    Ok(contents)
}


pub fn count_provinces() -> String {
    let input = read_file("district.json").unwrap();
    work(&input).iter().map(|x| x.to_string()).collect::<Vec<String>>().join(",")
}
